package jianzhi_offer;

import java.util.Arrays;

//第四题：给定一个二叉树的前序遍历和中序遍历。
//给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
public class Test4 {
    class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public int val;

        public TreeNode(int val) {
            this.left = null;
            this.right = null;
            this.val = val;
        }
    }

    @Override
    public String toString() {
        return "Test4{}";
    }

    //核心思想就是递归
    //先找找到头节点在中序遍历中的位置（index）。然后劈成两半，index左边就是左子树，右边就是右子树
    //而先序遍历中从头节点下一个开始（1）到此时中续遍历头节点的位置（i）就是左子树，后边部分就是右子树
    //！！！要注意的是进行递归构建左右子树的过程中。每一边的子树都需要拿到先序遍历和中序遍历的对应的左（右）子树。这里直接通过copyOfRange()方法获得（区间为左闭右开）。
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        if (preOrder == null || preOrder.length == 0) {
            return null;
        }
        // write code here
        TreeNode root = new TreeNode(preOrder[0]);

        if(preOrder.length == 1 && vinOrder.length == 1) {
            return root;
        }
        for(int i = 0;i < vinOrder.length;i++) {
            if(preOrder[0] == vinOrder[i]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder,1,i + 1),Arrays.copyOfRange(vinOrder,0,i));
                root.right = reConstructBinaryTree((Arrays.copyOfRange(preOrder,i + 1,preOrder.length)),Arrays.copyOfRange(vinOrder,i + 1,vinOrder.length));
                break;
            }
        }
        return root;

    }

    public void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7};
        int[] b = {3, 2, 4, 1, 6, 5, 7};
        TreeNode tree = reConstructBinaryTree(a,b);
        for(int i = 0;i < a.length;i++) {
            System.out.println(tree.val);
        }
    }
}

